package leetCode;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Set;
import data_structure.BTNode;

public class LeetCode_day11_tree {
	
	public static BTNode constructBSTFromSortedArray(int[] a, int start, int end){
		if(start > end) return null;
		int mid = start + (end - start)/2;
		BTNode root = new BTNode(a[mid]);
		root.left = constructBSTFromSortedArray(a, start, mid-1);
		root.right = constructBSTFromSortedArray(a, mid+1, end);
		return root;
	}
	
	public static void bstToSortedArray(BTNode root, List<BTNode> array){
		if(root == null) return;
		bstToSortedArray(root.left, array);
		array.add(root);
		bstToSortedArray(root.right, array);
	}
	
	/**
	 * !Catalan number
	 * 
	 * Cn is the number of full binary trees with n+1 leaves (notice, not binary search tree)
	 * 	  is the number of binary trees with n nodes
	 *    is the number of different ways n+1 factors can be completely parenthesized
	 *    (there are n-1 pairs of parentheses)
	 *    is the number of n pairs of parentheses which are correctly matched.
	 * 	  is the number of binary search tree
	 * 
	 * C(n+1) = sum_{i=0}^n C(i)C(n-i)
	 * C(0) = 1
	 * C(n+1) = 2(2n+1)/(n+2) C(n)
	 * 
	 * For binary search tree with sorted n nodes:
	 * picking a root i, left subtree is [1,i-1], right subtree is [i+1, n]
	 * The number of binary search tree rooted in i with n nodes is: N(i,n)
	 * N(i,n) = N(:,i-1) * N(:,n-i)
	 * N(:,n) = sum_{i=1}^n (N(:,i-1) * N(:,n-i)), N(0)=1, N(1)=1
	 * N(:,n) = (2n)!/n! *(n+1)!
	 * i.e. the sum of number of left subtree and right subtree 
	 * @param n
	 */
	public static void uniqueBinarySearchTrees(int n){
		int c = 1;
		for(int i = 2 ; i <= n ; i++)
			c = 2 * (2 * i - 1) * c /(i+1);
		System.out.println("There are " + c + " number of trees");
	}
	
	public static int uniqueBSTOriginal(int n){
		if(n == 0 || n == 1) return 1;
		int sum = 0;
		for(int i = 1 ; i <= n ; i++){
			        //left                    //right  
			sum += uniqueBSTOriginal(i-1) * uniqueBSTOriginal(n-i);
		}
		return sum;
	}
	
	public static int uniqueBSTDP(int n){
		int[] count = new int[n+1];
		count[0] = 1; count[1] = 1;
		if(n > 1){
			for(int j = 2 ; j <= n ; j++)
				for(int i = 1 ; i <= j ; i++)
					count[j] += count[i-1] * count[j-i];
		}
		return count[n];
	}
	
	/**
	 * !Given n, generate all structurally unique BST's (binary search trees) 
	 * that store values 1...n. For example,
	 * Given n = 3, your program should return all 5 unique BST
	 * 
	 * The basic idea is:
	 * Given the root, construct left subtree and right subtree and combine them
	 * 
	 * @param n
	 */
	public static List<BTNode> uniqueBinarySearchTreesII(int n){
		List<BTNode> result = new ArrayList<BTNode>();
		if(n == 0) result.add(new BTNode(null));
		else result = generateTrees(1, n);
		return result;
	}
	
	public static List<BTNode> generateTrees(int start, int end){
		List<BTNode> res = new ArrayList<BTNode>();//store all roots of different binary search tree
		if(start > end) res.add(new BTNode(null));
		else{
			for(int i = start ; i <= end ; i++){
				List<BTNode> leftsubtree = generateTrees(start,i-1);
				List<BTNode> rightsubtree = generateTrees(i+1, end);
				for(int j = 0 ; i < leftsubtree.size() ; j++)
					for(int k = 0 ; k < rightsubtree.size() ; k++){
						BTNode root = new BTNode(i);
						root.left = leftsubtree.get(j);
						root.right = rightsubtree.get(k);
						res.add(root);
					}
 			}
		}
		return res;
	}
	
	/**
	 * Given a binary tree, determine if it is a valid binary search tree (BST).
	 * Assume a BST is defined as follows:
	 * The left subtree of a node contains only nodes with keys less than the node's key.
	 * The right subtree of a node contains only nodes with keys greater than the node's key.
	 * Both the left and right subtrees must also be binary search trees.
	 * 
	 * Method: 
	 * Inorder traverse the tree and compare the left and right value with the root.
	 * @param root
	 */
	public static boolean validateBST(BTNode root){
		if(root == null) {
			return true;
		}
		else{
			boolean res1 = true;
			if(root.left != null){
				res1 = validateBST(root.left) && (root.val.doubleValue() > root.left.val.doubleValue()); 
			}
			boolean res2 = true;
			if(root.right != null){
				res2 = validateBST(root.right) && (root.val.doubleValue() < root.right.val.doubleValue()); 
			}
			return res1 && res2;
		}
	}
	
	/**
	 * !Two elements of a binary search tree (BST) are swapped by mistake.
	 * Recover the tree without changing its structure.
	 * Note:
	 * A solution using O(n) space is pretty straight forward.
	 * Could you devise a constant space solution?
	 * 
	 * The method using O(n) space is change the BST to an array,
	 * then find the two elements, the swap back.
	 */
	public static void recoverBinarySearchTree(BTNode root){
		BTNode[] candidates = new BTNode[2];
		System.out.println("**");
		inorderCheck(root, new BTNode[1], candidates);
		//swap values of the two candidates
		Number temp = candidates[0].val;
		candidates[0].val = candidates[1].val;
		candidates[1].val = temp;
	}
	/**
	 * ! Notice, here if we change the type pre from BSTNode[] to BSTNode
	 * The code: pre = root wouldn't work
	 * Because you cannot change the reference itself in function
	 * unless pre is a global variable, i.e. a field of LeetCode_tree class
	 * @param root
	 * @param pre
	 * @param candidates
	 */
	public static void inorderCheck(BTNode root, BTNode[] pre, BTNode[] candidates){
		if(root == null) return;
		inorderCheck(root.left, pre, candidates);
		if(pre[0] != null){
			System.out.println(pre[0].val);
			if(pre[0].val.doubleValue() > root.val.doubleValue()){
				if(candidates[0] == null) candidates[0] = pre[0];//find the first one
				else candidates[1] = root;//find the second one
			}
		}
		pre[0] = root;
		inorderCheck(root.right, pre, candidates);
	}
	
	/**
	 * Given two binary trees, write a function to check if they are equal or not.
	 * Two binary trees are considered equal if they are structurally identical 
	 * and the nodes have the same value.
	 * 
	 * @param root1
	 * @param root2
	 * @return
	 */
	public static boolean sameTree(BTNode root1, BTNode root2){
		if(root1 == null && root2 == null) return true;
		return root1.val.doubleValue() == root2.val.doubleValue() && 
				sameTree(root1.left , root2.left) &&
				sameTree(root1.right, root2.right);
	}
	
	/**
	 * Given a binary tree, check whether it is a mirror of itself 
	 * (ie, symmetric around its center).
	 *     1
	 *    / \
	 *   2   2
	 *  / \ / \
	 * 3  4 4  3
	 * @param root
	 * @return
	 */
	
	public static boolean symmetricTree(BTNode root1, BTNode root2){
		if(root1 == null && root2 == null) return true;
		return root1.val.doubleValue() == root2.val.doubleValue() &&
				symmetricTree(root1.left, root2.right) &&
				symmetricTree(root1.right , root2.left);
	}
	
	/**
	 * !
	 * Method 1: two queue, one store this level, and next store next level
	 * 			 after printing this level, swap the two queue, printing next level
	 * Method 2: (less space) dummy variable to indicate the levels
	 * @param root
	 */
	public static void binaryTreeLevelOrderTraversal(BTNode root){
		if(root == null) return;
		Queue<BTNode> q = new LinkedList<BTNode>();
		List<List<BTNode>> levels = new ArrayList<List<BTNode>>();
		q.offer(root);
		q.offer(new BTNode(null));//first level
		levels.add(new ArrayList<BTNode>());
		int ind = 0;
		while(!q.isEmpty()){
			BTNode node = q.poll();
			if(node.val == null && !q.isEmpty()){//when last level ended, next level stated
				levels.add(new ArrayList<BTNode>());
				ind++;
				q.offer(new BTNode(null));
				node = q.poll();
			}
			if(node.val == null) continue;
			levels.get(ind).add(node);// store nodes of this level
			if(node.left != null || node.right != null){//offer nodes from next level
				if(node.left != null) q.offer(node.left);
				if(node.right != null) q.offer(node.right);
			}
		}
		
		//levels.remove(levels.size() - 1);
		for(int i = 0 ; i < levels.size() ; i++){
			System.out.println("level "+i);
			for(BTNode node:levels.get(i))
				System.out.print(node.val+" ");
			System.out.println();
		}
 	}
	
	
	
	public static int maximumDepthOfBinaryTree(BTNode root){
		if(root == null) return 0;
		return 1+(Math.max(maximumDepthOfBinaryTree(root.left), maximumDepthOfBinaryTree(root.right)));
	}
	
	/**
	 * Given preorder and inorder traversal of a tree, construct the binary tree.
	 * 
	 * Notice: duplicates are not allowed in assumption
	 * If  preorder = {7,7} = inorder, there would be two trees there (ambiguity)
	 * 
	 * preorder: root->left->right
	 * inorder:  left->root->right
	 * 
	 * the first element in preorder is the root of the whole tree
	 * We can:
	 * 	Using preorder to identify root
	 * 	Using inorder to identify subtrees of the root
	 * 
	 * 				 5
	 * 			  /      \
	 * 			 3        9
	 *          / \     /   \
	 *         2   4   7     11
	 *        /       / \   /
	 *       1       6   8 10
	 * 
	 * @param preorder
	 * @param inorder
	 * @return
	 */
	public static BTNode constructBinaryTreeFromPreorderAndInorderTraversal(int[] preorder, int[] inorder){
		if(preorder == null || inorder == null) return null;
		return constructBTPreInorder(preorder, inorder, 0, preorder.length-1, 0, inorder.length-1);
	}
	
	public static BTNode constructBTPreInorder(int[] preorder, int[] inorder, int prestart, int preend, int instart, int inend){
		BTNode root = new BTNode(preorder[prestart]);
		
		int ind = -1;
		for(int i = instart ; i <= inend ; i++)
			if(inorder[i] == preorder[prestart]){
				ind = i; break;
			}
		
		int leftPreend = prestart;
		
		if(ind == instart) {//no left
			root.left = null;
		}else{
			//left
			int leftPrestart = prestart+1;
			int leftInstart = instart, leftInend = ind-1;
			//for(int i = leftInend ; i >= instart ; i--)
				//leftPreend++;
			leftPreend = leftPrestart+leftInend-leftInstart;
			root.left = constructBTPreInorder(preorder, inorder, leftPrestart, leftPreend, leftInstart, leftInend);
		}
		
		if(ind == inend) root.right = null;//no right
		else{
			int rightPrestart = leftPreend + 1, rightPreend = preend;
			int rightInstart = ind + 1, rightInend = inend;
			root.right = constructBTPreInorder(preorder, inorder, rightPrestart, rightPreend, rightInstart, rightInend);
		}//*/
		
		return root;
	}
	
	
	/**
	 * postorder: left->right->root
	 * inorder: left->root->right
	 * 
	 * the last element of postorder is the root of the whole tree
	 * We can:
	 * 	Using postorder to identify root
	 * 	Using inorder to identify subtrees of the root
	 * @param inorder
	 * @param postorder
	 * @return
	 */
	public static BTNode constructBinaryTreeFromPostorderAndInorderTraversal(int[] inorder, int[] postorder){
		if(inorder == null || postorder == null) return null;
		return constructBTPostInorder(postorder, inorder, 0, postorder.length-1 , 0 , inorder.length-1);
	}

	public static BTNode constructBTPostInorder(int[] postorder, int[] inorder, int poststart, int postend,
			int instart, int inend){
		BTNode root = new BTNode(postorder[postend]);
		
		int ind = -1;
		for(int i = instart ; i <= inend ; i++)
			if(inorder[i] == postorder[postend]){
				ind = i;
				break;
			}
		
		int leftinstart = instart , leftinend = ind-1;
		int leftpoststart = poststart, leftpostend = leftpoststart+leftinend-leftinstart;
		if(instart == ind) {
			root.left = null;//TODO
			leftpostend = instart;
		}
		else root.left = constructBTPostInorder(postorder, inorder, leftpoststart, leftpostend, leftinstart, leftinend);
		
		int rightinstart = ind+1, rightinend = inend;
		int rightpoststart = leftpostend+1 , rightpostend = postorder.length-2;
		if(inend == ind) root.right = null;
		else constructBTPostInorder(postorder, inorder, rightpoststart, rightpostend, rightinstart, rightinend);
		return root;
	}
	

	
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		/*uniqueBinarySearchTrees(3);
		System.out.println(uniqueBSTOriginal(2));
		System.out.println(uniqueBSTDP(3));
		System.out.println();
		BTNode root = constructBSTFromSortedArray(new int[]{1,2,3,4,5,6,7,8}, 0, 7);
		BTNode root1 = constructBSTFromSortedArray(new int[]{1,2,6,4,5,3,7,8}, 0, 7);
		System.out.println(validateBST(root1));
		List<BTNode> array = new ArrayList<BTNode>();
		recoverBinarySearchTree(root1);
		bstToSortedArray(root1, array);
		System.out.println();
		for(BTNode b : array)
			System.out.print(b.val);
		System.out.println();
		System.out.println("Same tree?"+sameTree(root,root1));
		
		
		BTNode symeTree = new BTNode(1);
		BTNode temp1 = new BTNode(2);
		BTNode temp2 = new BTNode(2);
		BTNode temp3 = new BTNode(3);
		BTNode temp4 = new BTNode(3);
		BTNode temp5 = new BTNode(4);
		BTNode temp6 = new BTNode(4);
		symeTree.left = temp1; symeTree.right = temp2;
		temp1.left = temp3; temp1.right = temp5;
		temp2.left = temp6; temp2.right = temp4;
		
		System.out.println("Symmetric? "+ symmetricTree(symeTree, symeTree));
		binaryTreeLevelOrderTraversal(symeTree);
		System.out.println("Max height is: "+ maximumDepthOfBinaryTree(symeTree));//*/
		
		int[] preorder = new int[]{5,3,2,1,4,9,7,6,8,11,10};
		int[] inorder = new int[]{1,2,3,4,5,6,7,8,9,10,11};//*/
		int[] postorder = new int[]{1,2,4,3,6,8,7,10,11,9,5};
		BTNode newroot = constructBinaryTreeFromPreorderAndInorderTraversal(preorder, inorder);
		System.out.println();
		binaryTreeLevelOrderTraversal(newroot);
		BTNode newroot1 = constructBinaryTreeFromPostorderAndInorderTraversal(inorder, postorder);
		System.out.println();
		binaryTreeLevelOrderTraversal(newroot1);
	}
}

